/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package geometry;

import java.util.ArrayList;
import java.util.Stack;

/**
 *
 * @author rusak
 */
public class GrahamAlgorithm implements ConvexHullAlgorithm {
//Zakladamy, ze poczatek pierwszego segmentu jest najnizej w sortowaniu katowym.

    @Override
    public Obstacle computeHull(Obstacle obstacle) {
        Stack<Vertex> stack = new Stack<Vertex>();
        stack.push(obstacle.getEdgeAt(0).getBegin());
        stack.push(obstacle.getEdgeAt(0).getEnd());
        int i = 1;
        int size = obstacle.size();
        boolean first = true;
        Vertex onStack1, onStack2;
        //System.out.println("OBSTACLE!");
        while (i <= size) {
            onStack1 = stack.pop();
            onStack2 = stack.peek();
            
            

            if (i != size) {
              //  System.out.println("ON STACK: "+obstacle.getEdgeAt(i).getEnd()+"  "+onStack1+"  "+onStack2);
                while ((first || stack.size() > 1) && (!toTheLeft(onStack2, onStack1, obstacle.getEdgeAt(i).getEnd()))) {
                    onStack1 = stack.pop();
                    if(!first) {
                    onStack2 = stack.peek();}
                    first = false;
                }
                stack.push(onStack1);
                stack.push(obstacle.getEdgeAt(i).getEnd());
                
            }else {
              //  System.out.println("ON STACK: "+obstacle.getEdgeAt(0).getBegin()+"  "+onStack1+"  "+onStack2);
                while (stack.size() > 1 && !toTheLeft(onStack2, onStack1, obstacle.getEdgeAt(0).getBegin())) {
                    onStack1 = stack.pop();
                    onStack2 = stack.peek();

                }
                stack.push(onStack1);
                
            }
            i++;
        }


        Segment segs[] = new Segment[stack.size()-1];
       // Vertex last = stack.peek();
        Vertex v1, v2 = new Vertex(0, 0);
        for (int j = segs.length - 1; j >= 0; j--) {
            v1 = stack.pop();
      //      System.out.println("FROM STACK: "+v1);
            v2 = stack.peek();
            segs[j] = new Segment(v2, v1);

        }
        
       // segs[segs.length - 1] = new Segment(last, v2);
        
        return new Obstacle(segs);
    }

    //zakladamy, ze segmenty s1 i s2 to kolejne segmenty na brzegu - koniec s1 to poczatek s2
    //Zakladamy tez, ze zadne dwa kolejne boki nie sa wspolliniowe. 
    private boolean toTheLeft(Vertex a, Vertex b, Vertex c) {


        double result = (c.getX() - a.getX()) * (b.getY() - a.getY())
                - (b.getX() - a.getX()) * (c.getY() - a.getY());
        return result <= 0;
    }
}
